# 530.二叉搜索树的最小绝对差
# 给你一个二叉搜索树的根节点root ，返回树中任意两不同节点值之间的最小差值 。
# 差值是一个正数，其数值等于两值之差的绝对值。
#
# 示例1：
# 输入：root = [4, 2, 6, 1, 3]
# 输出：1
#
# 示例2：
# 输入：root = [1, 0, 48, null, null, 12, 49]
# 输出：1


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def getMinimumDifference(self, root:[TreeNode]) -> int:
        # 直接转换成数组，很好比较
        res = []
        def inorder(root):
            if not root:
                return
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
            return res
        tmp = inorder(root)
        size = len(tmp)
        minus = tmp[-1]
        for i in range(1,size):
            diff = tmp[i] - tmp[i-1]
            if diff < 0:
                diff = - diff
            minus = min(minus,diff)
        return minus

    # 重点掌握双指针法，不过这个还没看，先记录下
    def getMinimumDifference2(self, root: TreeNode) -> int:
        stack = []
        cur = root
        pre = None
        result = float('inf')
        while cur or stack:
            if cur: # 指针来访问节点，访问到最底层
                stack.append(cur)
                cur = cur.left
            else: # 逐一处理节点
                cur = stack.pop()
                if pre: # 当前节点和前节点的值的差值
                    result = min(result, abs(cur.val - pre.val))
                pre = cur
                cur = cur.right
        return result

if __name__ == '__main__':
    #      4
    #   2      7
    # 1   3
    a31 = TreeNode(1)
    a32 = TreeNode(3)
    a21 = TreeNode(2,a31,a32)
    a22 = TreeNode(7)
    a11 = TreeNode(4,a21,a22)
    tmp = Solution()
    res1 = tmp.getMinimumDifference(a11)
    print(res1)